PGCD et algorithme d'Euclide - Corrigé

Énoncé

  Utiliser l'algorithme d'Euclide pour calculer le PGCD des nombres suivants.

1. $255$ et $189$

2. $1260$ et $3234$

3. $8008$ et $4095$

4. $783$ et  $1395$

Solution

1. On utilise l'algorithme d'Euclide :

$\begin{array}{r}\begin{array}{|cccc|}\hline a& b& q& r\\ 255& 189& 1& 66\\ 189& 66& 2& 57\\ 66& 57& 1& 9\\ 57& 9& 6& 3\\ 9& 3& 3& 0\\ \hline\end{array}\end{array}$  

donc $\mathrm{PGCD}(255;189)=3$ .

2. On utilise l'algorithme d'Euclide :

$\begin{array}{r}\begin{array}{|cccc|}\hline a& b& q& r\\ 3234& 1260& 2& 714\\ 1260& 714& 1& 546\\ 714& 546& 1& 168\\ 546& 168& 3& 42\\ 168& 42& 4& 0\\ \hline\end{array}\end{array}$  

donc $\mathrm{PGCD}(1260;3234)=42$ .

3. On utilise l'algorithme d'Euclide :

$\begin{array}{r}\begin{array}{|cccc|}\hline a& b& q& r\\ 8008& 4095& 1& 3913\\ 4095& 3913& 1& 182\\ 3913& 182& 21& 91\\ 182& 91& 2& 0\\ \hline\end{array}\end{array}$  

donc $\mathrm{PGCD}(8008;4095)=91$ .

4. On utilise l'algorithme d'Euclide :

$\begin{array}{r}\begin{array}{|cccc|}\hline a& b& q& r\\ 1395& 783& 1& 612\\ 783& 612& 1& 171\\ 612& 171& 3& 99\\ 171& 99& 1& 72\\ 99& 72& 1& 27\\ 72& 27& 18& 9\\ 27& 9& 3& 0\\ \hline\end{array}\end{array}$  

donc $\mathrm{PGCD}(783;1395)=9$ .